The proliferation of digital media such as digital images, audio, video, and text images (documents) has generated significant interest in copyright protection, image annotation, and authentication. Watermarking (also referred to as data hiding) has been identified as a promising mechanism for copyright protection, annotation, and authentication. Watermarking promises the ability to embed inalterable watermark data directly in a digital file. At a later time, the data may be extracted to identify the origin of the digital file and verify its authenticity.
Typically, watermarking an image is achieved by changing a portion of the visible image. For example, single pixels within an image may be modified in order to transport data. Embedding watermark data in binary images, however, has presented significant challenges as arbitrarily changing pixels in such images is easily noticed.
Nevertheless, numerous data-hiding methods for embedding watermark data in binary documents have been proposed. For example, Min Wu, Edward Tang and Bede Liu, “Data Hiding in Digital Binary Image”, IEEE International Conference on Multimedia and Expo., 2000, pp. 393-396 proposes dividing an image into blocks, and locating the most suitable pixel within each block to embed watermark data. A list, based on the block size (for example, based on 3×3 blocks), is used to rank the pixels in blocks in order of appropriateness for inverting or “flipping” the pixel. Such ranking, however, is quite subjective and may lead to mixed results depending on the image as a whole. Therefore, pixels in the image are randomly rearranged (“shuffled”) to handle uneven distribution of inverted pixels in the image. The shuffled image is divided into blocks and one bit is embedded in each block in the shuffled image by inverting the “flippable” pixels which is determined by the list. Moreover, for small blocks (e.g., 8×8 pixels), it is difficult to find a suitable shuffle key to ensure that every block in the shuffled domain has at least one “flippable” pixel. As a consequence, the final result is often not pleasing, as less than ideal pixels may be flipped in some blocks, salt-and-pepper noise, or erosion will be created in this case. On the other hand, for large block sizes (e.g.16×16) only one bit is embedded in each block and the number of “flippable” pixels available to transport the hidden data is low.
Watermarking or data hiding on binary images can be classified into several categories, e.g., fragile or semi-fragile and robustness watermarks. Based on the domain used for watermarking or data hiding, it can be categorized into spatial domain techniques and transform domain techniques.
U.S. patent application Ser. No. 10/958,033, for example, discloses a method of searching for bits within a two color image that may be inverted without perceptibly affecting the nature of the image. The method proceeds by searching for specific patterns in the image. As the method operates directly on the image without transforming the image, the technique is said to operate in image space.
Image space techniques can be generally classified into several classes: text line, word or character shifting, boundary modifications, fixed block partitioning, modification of character features, modification of run-length patterns and modification of halftone images as seen in M. Chen, E. K. Wong, N. Memon and S. Adams, “Recent Development in Document Image Watermarking and Data Hiding”, Proc. SPIE Conf. 4518: Multimedia Systems and Applications IV, pp. 166-176, August 2001. An early work on data hiding for binary images which enforces the ratio of black vs. white pixels in a block to be larger or smaller than one is proposed in J. Zhao and E. Koch, “Embedding Robust Labels into Images for Copyright Protection”, Proc. of the Int. Congress on Intellectual Property Rights for Specialized Information, Knowledge and New Technologies, pp. 1-10, Vienna, August 1995. A group of continuous or distributed blocks are modified by switching white pixels to black and vice versa until such thresholds are reached. Modifications of the pixels are done either on the boundary of pixels, e.g., for common text documents, or distributed throughout the whole block, e.g., for dithered images. The technique is not secure enough to be directly applied for authentication and the capacity is limited by enforcing a certain percentage of black pixels.
Several pattern-based methods are discussed in for example Min Wu, E. Tang and B. Liu, “Data Hiding in Digital Binary Image”, IEEE International Conf. on Multimedia and Expo., 2000, pp. 393-396; Min Wu, and Bede Liu, “Data Hiding in Binary Images for Authentication and Annotation”, IEEE Transactions on Multimedia, Vol. 6, No. 4, pp. 528-538, August 2004; H. Yang and Alex C. Kot, “Data hiding for Bi-level Documents Using Smoothing Techniques”, Proceedings of the 2004 International Symposium on Circuits and Systems (ISCAS'04), Vol. 5, pp. 692-695, May 2004; and H. Yang and Alex C. Kot, “Date Hiding for Text Document Image Authentication by Connectivity-Preserving”, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 2, pp. 505-508, Mar. 18-23, 2005, Philadelphia, Pa., USA. These methods mainly look for the patterns in 3×3 or 5×5 neighborhood.
A fixed block partition method proposed by Tseng et al. (in H.-K. Pan, Y.-Y. Chen and Y.-C. Tseng, “A Secure Data Hiding Scheme for Two-Color Images,” Proceedings of the Fifth Symposium on Computers and Communications, pp. 750-755, Jul. 3-6, 2000.) uses a secret key and a weight matrix to protect the hidden data. Given an image with block size of m×n, the scheme can hide as many as └log2(mn+1)┘ bits of data. However, the visual effects of the scheme are poor because of the randomness in choosing the locations for flipping. The watermarked document appears to be noisy.
Other embedding techniques require an image to be transformed from image space into some other space. An early investigation of combined spatial and frequency domain approach is proposed by Y. Liu, J. Mant, E. Wong and S. H. Low, “Marking and Detection of Text Documents Using Transform-domain Techniques”; Proc. of SPIE, vol. 3657, Electronic Imaging (EI'99) Conf. on Security and Watermarking of Multimedia Contents, pp. 317-328, San Jose, Calif., 1999, in which the watermark embedding is done in spatial domain by using the line or word shifting method whereas the watermark detection is done in frequency domain by using Cox et al.'s method. The idea is based on the observation that the watermarking effect on text document images in frequency domain is more obtrusive than pictorial image. It always creates a “dirty” background. “Cleaning” the background by thresholding light grays to white renders the watermark less obtrusive but also sharply reduces the detector response.
A further investigation of watermarking on binary images based discrete cosine transform DC components is proposed in H. Lu, X. Shi, Shi, Y. Q., Kot A. C. and L. Chen, “Watermark embedding in DC Components of DCT for binary images”, The 2002 IEEE Workshop on Multimedia Signal Processing, pp. 300-303, 9-11, Dec. 2002. A preprocessing step of blurring and a post-processing step of biased binarization are required in order to embed the watermark successfully into the binary image. However, the experimental results show that the watermarked image has poor quality due to the pre-blurring and post-binarization process.
All of these techniques present their own benefits and disadvantages. As such, there is a need for other techniques of embedding data in two color images.